#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct BSTNode
{
    int data;
    struct BSTNode *lchild;
    struct BSTNode *rchild;
}BSTNode, *BSTree;

static BSTNode* IniNode(int data);
bool Search(BSTree bst, int key, BSTree f, BSTree *p);
bool Insert(BSTree *bst, int key);
void preOrder(BSTree bst);
void inOrder(BSTree bst);
void postOrder(BSTree bst);
void printOrder(BSTree bst);

void shuru(int n, int *array)
{
    int i = 0;
    for(; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
}

int main()
{
    int m;
    int count=0;
    int *array;
    int* arrAdr[100];
    int num[100];
    while(scanf("%d", &m) != EOF)
    {
        array = (int*)calloc(m,sizeof(int));
        shuru(m, array);
        arrAdr[count]=array;
        num[count]=m;
        count++;
    }
    int k = 0;
    for(; k < count; k++)
    {
        int j = 0;
        BSTNode *bst = NULL;
        for (; j < num[k]; j++)
        {
            Insert(&bst, arrAdr[k][j]);
        }
        printOrder(bst);
    }
    return 0;
}

static BSTNode* IniNode(int data)
{
    BSTNode *pTmp = (BSTNode*)malloc(sizeof(BSTNode));
    if(NULL == pTmp)
    {
        exit(0);
    }
    pTmp->data = data;
    pTmp->lchild = NULL;
    pTmp->rchild = NULL;
    return pTmp;
}

bool Search(BSTree bst, int key, BSTree f, BSTree *p)
{
    // bst为搜索节点，f为上一个节点
    if (!bst)
    {
        *p = f;
        return false;
    }
    if (bst->data == key)
    {
        *p = bst;
        return true;
    }
    else if (bst->data < key)
    {
        return Search(bst->rchild, key, bst, p);
    }
    return Search(bst->lchild, key, bst, p);
}

bool Insert(BSTree *bst, int key)
{
    if (NULL == *bst)
    {
        *bst = IniNode(key);    // 插入根节点
        return true;
    }
    BSTNode *p;	// p为要寻找插入的节点位置
    if (!Search(*bst, key, NULL, &p))
    {
        BSTNode *pNew = IniNode(key);
        if (key < p->data)
        {
            p->lchild = pNew;
        }
        else if (key > p->data)
        {
            p->rchild = pNew;
        }
        return true;
    }
    else
    {
        ;
    }
    return false;
}

void preOrder(BSTree bst)
{
    if (NULL != bst)
    {
        printf("%d ", bst->data);
        preOrder(bst->lchild);
        preOrder(bst->rchild);
    }
    // printf("pre\n");
}

void inOrder(BSTree bst)
{
    if (NULL != bst)
    {
        inOrder(bst->lchild);
        printf("%d ", bst->data);
        inOrder(bst->rchild);
    }
    // printf("in\n");
}

void postOrder(BSTree bst)
{
    if (NULL != bst)
    {
        postOrder(bst->lchild);
        postOrder(bst->rchild);
        printf("%d ", bst->data);
    }
    // printf("post\n");
}

void printOrder(BSTree bst)
{
    preOrder(bst);
    printf("\n");
    inOrder(bst);
    printf("\n");
    postOrder(bst);
    printf("\n");
}
